﻿#include <iostream>
#include <vector>

using namespace std;

int findTargetSumWays(vector<int>& nums, int target) 
{
	int sum = 0;					
	for (auto x : nums) sum += x;
	int aim = (sum + target) / 2;
	// 处理⼀下边界条件
	if (aim < 0 || (sum + target) % 2) return 0;
	int n = nums.size();
	vector<vector<int> > dp(n + 1, vector<int>(aim + 1));	// 表示在前i个数中选，总和等于j，有多少种选法
	dp[0][0] = 1;											// 初始化
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= aim; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= nums[i - 1])
			{
				dp[i][j] += dp[i - 1][j - nums[i - 1]];
			}
		}
	return dp[n][aim];
}

int findTargetSumWays(vector<int>& nums, int target)
{
	int sum = 0;
	for (auto x : nums) sum += x;
	int aim = (sum + target) / 2;
	// 处理⼀下边界条件
	if (aim < 0 || (sum + target) % 2) return 0;
	int n = nums.size();
	vector<int> dp(aim+1);	// 表示在前i个数中选，总和等于j，有多少种选法
	dp[0] = 1;				// 初始化
	for (int i = 1; i <= n; i++)
		for (int j = aim; j >= nums[i - 1]; j--)
		{
			dp[j] += dp[j - nums[i - 1]];
		}
	return dp[aim];
}
int main()
{
	vector<int> v = { 1,1,1,1,1 };

	cout << findTargetSumWays(v, 3) << endl;

	return 0;
}